package com.faxon.leetcode.f;

import org.junit.Test;

/**
 * @author Faxon
 * @version 1.0
 * @date 2020-04-16 16:03
 * 53. 最大子序和
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 示例:
 * 输入: [-2,1,-3,4,-1,2,1,-5,4],
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 **/
public class LeetCode53 {

    public int maxSubArray(int[] nums) {
        //贪心法
        int greedy = greedy(nums);
        //分治法
        int decursive = decursive(nums, 0, nums.length - 1);
        //动态规划
        return 0;
    }

    /**
     * 递归求解（分治法）。
     *
     * @param nums  数组
     * @param left  左半部分最左下标(数组的第一个元素下标)
     * @param right 右半部分最右下标(数组的最后一个元素下标)
     * @return
     */
    public int decursive(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        //数组的中间部分下标
        int mid = (left + right) / 2;
        int leftSum = decursive(nums, left, mid);
        int rightSum = decursive(nums, mid + 1, right);
        int currSum = currSum(nums, left, mid, right);
        return Math.max(Math.max(leftSum, rightSum), currSum);
    }

    /**
     * 分治法中求跨越中间索引的最长子序列和
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     * @return
     */
    public int currSum(int[] nums, int left, int mid, int right) {
        if (left == right) {
            return nums[left];
        }
        int leftSum = 0, leftMax = Integer.MIN_VALUE;
        for (int i = mid; i >= left; i--) {
            leftSum += nums[i];
            leftMax = Math.max(leftSum, leftMax);
        }
        int rightSum = 0, rightMax = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= right; i++) {
            rightSum += nums[i];
            rightMax = Math.max(rightSum, rightMax);
        }
        return leftMax + rightMax;
    }

    /**
     * 贪心算法
     *
     * @return
     */
    public int greedy(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int currySum = nums[0], maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currySum = Math.max(nums[i], currySum + nums[i]);
            maxSum = Math.max(maxSum, currySum);
        }
        return maxSum;
    }

    @Test
    public void testMaxSubArray() {
        int[] nums = new int[]{-2,-1};
        //贪心法
//        int greedy = greedy(nums);
        //分治法
        int decursive = decursive(nums, 0, nums.length - 1);
//        System.out.println(greedy);
        System.out.println(decursive);
    }
}
